42587 - 과제 진행하기

info

• 문제 보기: 176962 - 과제 진행하기
• 소요 시간: 20분 42초
• 풀이 언어: java
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

스택 정렬 시뮬레이션

풀이 코드

info

• 메모리: 98900 KB
• 시간: 9 ms

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        // convert to object
        List<Plan> pList = new ArrayList<>();
        for (String[] p : plans) {
            String[] hm = p[1].split(":");
            int cvtStart = Integer.parseInt(hm[0])*60 + Integer.parseInt(hm[1]);
            pList.add(new Plan(p[0], cvtStart, Integer.parseInt(p[2])));
        }
        
        // sort asc by start time
        Collections.sort(pList, (a, b) -> a.start - b.start);
        
        // simulate
        Deque<Plan> st = new ArrayDeque<>(); // stack: for pause
        String[] ans = new String[plans.length];
        
        int idx = 0;
        int adx = 0; // ans idx
        int n = pList.size();
        Plan curPlan; // current working plan
        while (idx < n) {
            curPlan = pList.get(idx);
            int s = curPlan.start;
            int pt = curPlan.playtime;
            int nxtS = (idx+1 < n) ? pList.get(idx+1).start : Integer.MAX_VALUE;

            // interrupt
            if (s + pt > nxtS) {
                int remain = s + pt - nxtS;
                curPlan.playtime = remain;
                st.push(curPlan);
                ++idx;
            }
            // 끝까지 수행 가능
            else {
                ans[adx++] = curPlan.name;
                int t = s + pt; // current time

                // resume paused (skip if none)
                while (!st.isEmpty()) {
                    Plan paused = st.pop();
                    if (t + paused.playtime <= nxtS) {
                        t += paused.playtime;
                        ans[adx++] = paused.name;
                    } else {
                        paused.playtime -= nxtS-t;
                        st.push(paused);
                        break;
                    }
                }

                ++idx;
            }
        }
        
        return ans;
    }
    
    class Plan {
        String name;
        int start; // unit: min
        int playtime;

        Plan(String n, int s, int pt) {
            name = n;
            start = s;
            playtime = pt;
        }
    }
}

풀이 해설

WIP